package com.wu.haspath;

/**
 * 矩阵中的路径
 */
public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        //构建二维数组
        char[][] board = new char[rows][cols];
        int index = 0;
        int x = 0;
        for (int i = 0; i < matrix.length; i++) {
            if (index >= cols) {
                index = 0;
                x++;
            }
            board[x][index] = matrix[i];
            index++;
        }
        boolean[][] vis = new boolean[rows][cols];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, str, i, j, vis, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] str, int x, int y, boolean[][] vis, int index) {
        //上下左右都走不通
        if (x < 0 || x>= board.length || y < 0 || y >= board[0].length || vis[x][y]){
            return false;
        }
        //找到第一个匹配的位置
        if (str[index] != board[x][y]){
            return false;
        }
        //匹配到最后一个单词
        if (index == str.length - 1){
            return true;
        }
        //先标记已访问
        vis[x][y] = true;
        boolean flag = dfs(board, str, x + 1, y, vis, index + 1) ||
                dfs(board, str, x - 1, y , vis, index + 1) ||
                dfs(board, str, x, y + 1, vis, index + 1) ||
                dfs(board, str, x, y - 1, vis, index + 1);
        //走不通，则回溯
        vis[x][y] = false;
        return flag;
    }
}